//
// Created by Administrator on 2022/1/26.
//

#ifndef CPP_LEARNING_LEETCODE23_H
#define CPP_LEARNING_LEETCODE23_H
#include <vector>
using namespace std;
#include <math.h>
#include <iostream>
#include <queue>
#include <functional>
#include "listnode.h"

using QueueItem = std::pair<int, ListNode*>;

struct ListNodeCompare{
    bool operator()(QueueItem&a,QueueItem& b){
        return a.second->val > b.second->val;
    }
};
class Solution23 {
public:
    // 得到最低的那个的序列
    // -1 没有最低的序列
    //    int getMinIndex(vector<ListNode*>& lists){
    //        int minIndex = -1;
    //        int minValue = INT32_MAX;
    //        for(int i=0; i<lists.size(); i++){
    //            if(lists[i] != nullptr && lists[i]->val < minValue){
    //                minValue = lists[i]->val;
    //                minIndex = i;
    //            }
    //        }
    //
    //        return minIndex;
    //    }
    //    ListNode* mergeKLists(vector<ListNode*>& lists) {
    //        int minIndex = getMinIndex(lists);
    //        ListNode* root = nullptr;
    //        ListNode* curNode = nullptr;
    //        while(minIndex != -1){
    //            ListNode* node = lists[minIndex];
    //            if(root == nullptr){
    //                root = node;
    //                curNode = node;
    //            }else{
    //                curNode->next = node;
    //                curNode = node;
    //            }
    //            lists[minIndex] = node->next;
    //            node->next = nullptr;
    //
    //            minIndex = getMinIndex(lists);
    //        }
    //
    //        return root;
    //    }


    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<QueueItem, vector<QueueItem>, ListNodeCompare> minQueue;

        for(int i=0; i<lists.size(); i++){
            ListNode* node = lists[i];
            if(node != nullptr){
                lists[i] = node->next;
                node->next = nullptr;
                minQueue.push(std::make_pair(i, node));
            }
        }

        ListNode* root = nullptr;
        ListNode* curNode = nullptr;
        while(! minQueue.empty()){
            auto queueItem = minQueue.top();
            minQueue.pop();
            if(root == nullptr){
                root = queueItem.second;
                curNode = queueItem.second;
            }else{
                curNode->next = queueItem.second;
                curNode = queueItem.second;
            }

            // 加入
            int i = queueItem.first;
            ListNode* node = lists[i];
            if(node != nullptr){
                lists[i] = node->next;
                node->next = nullptr;
                minQueue.push(std::make_pair(i, node));
            }
        }

        return root;
    }
};

void test23(){
    Solution23 s;
    ListNode* n11= new ListNode(1);
    ListNode* n14 = new ListNode(4);
    ListNode* n15= new ListNode(5);
    n11->next = n14;
    n14->next = n15;

    ListNode* n21 = new ListNode(1);
    ListNode* n23 = new ListNode(3);
    ListNode* n24 = new ListNode(4);
    n21->next = n23;
    n23->next = n24;

    ListNode* n32 = new ListNode(2);
    ListNode* n36 = new ListNode(6);
    n32->next = n36;

    vector<ListNode*> lists = {n11, n21, n32};
    s.mergeKLists(lists);


}

#endif //CPP_LEARNING_LEETCODE977_H
